Мутация белка - 1

Ограничение времени1 секунда
Ограничение памяти1024 Мб
Вводстандартный ввод или input.txt
Выводстандартный вывод или output.txt

Максимальная оценка за эту задачу — 40 баллов, на проверку необходимо сдавать программу, решающую задачу

РНК можно рассматривать как длинную цепочку, составленную из нуклеотидов. В этой задаче нуклеотидом будем называть один из символов ‘U’, ‘C’, ‘A’, ‘G’. Три подряд идущих нуклеотида образуют кодон (порядок нуклеотидов в кодоне важен). Каждому кодону соответствует некоторая аминокислота, при этом нескольким различным кодонам может соответствовать одна и та же аминокислота:

image
Соответствие кодонов аминокислотам

Выберем первый нуклеотид в центре, далее будем переходить на следующее кольцо по соответствующему нуклеотиду, соседнему со стороной фигуры.

Например, «AUG» — это кодон, который соответствует аминокислоте ‘M’.

Обратите внимание, что старт кодон выглядит как «AUG», а стоп кодон — это один из вариантов: «UAA», «UAG», «UGA».

Будем говорить, что белок — это последовательность аминокислот, которая начинается с аминокислоты ‘M’ и заканчивается одной из аминокислот, являющихся стоп-кодоном (такие аминокислоты обозначены в таблице кружком). Стоп-кодон не может встречаться в середине белка. Аминокислота ‘M’, напротив, может встречаться несколько раз.

Биолог исследует белок длины n n . При синтезе РНК произошла ошибка: в неё было вставлено ещё k k нуклеотидов в произвольные места. В результате получилась последовательность из 3 n + k 3n + k нуклеотидов, и биолог хочет восстановить какой-нибудь белок длины n n .

Формат ввода

В первой строке записано одно целое число t t — количество наборов входных данных. В этой версии задачи во всех тестах t = 1 t=1 .

Во 2 ⋅ ( t + 1 ) 2\cdot (t + 1) -й строке записаны два целых числа n n и k k ( 2 ≤ n ≤ 1 05 2 \le n \le 10^5 , 1 ≤ k ≤ 1 05 1 \le k \le 10^5 ).

В 2 ⋅ ( t + 1 ) + 1 2\cdot (t + 1) + 1 -й строке записана строка длины 3 n + k 3n + k , которая является последовательностью нуклеотидов. Гарантируется, что строка содержит только символы ‘U’, ‘C’, ‘A’, ‘G’.

Формат вывода

Выведите t t строк, в каждой из них k k различных целых чисел — номера удаляемых нуклеотидов в тесте t t . Номера можно выводить в любом порядке.

Система оценивания

В этой версии задачи 40 40 тестов помимо тестового примера из условия, каждый оценивается в 1 1 балл. Тестовый пример не оценивается.

Длина восстановленного белка l e n len определяется следующим образом.

Рассмотрим строку, полученную после удаления некоторых нуклеотидов, и разобьём её на кодоны. Затем найдём первое вхождение старт-кодона и первое вхождение стоп-кодона, расположенное после него. Тогда длиной белка будем считать количество аминокислот от ‘M’ до этого стоп-кодона включительно.

Количество баллов за тест определяется по формуле s c o r e = l e n n . score = \frac{len}{n}.

Обратите внимание, что если у вас выполнится одно из трёх условий:

  1. Нет ни одного старт кодона

  2. Нет ни одного стоп кодона

  3. Все старт кодоны находятся после всех стоп кодонов

То вы получите 0 0 баллов за тест.

Подзадача Баллы Доп. ограничения
0 0 тесты из условия
1 8 2 ≤ n ≤ 6 2 \le n \le 6 , 1 ≤ k ≤ 6 1 \le k \le 6
2 8 k = 1 k = 1
3 8 k = 2 k = 2
4 8 k = 3 k = 3
5 8 Вставка происходит только между соседними кодонами

Пример

ВводВывод
1
2 1
AUUGUGA

3

Примечания

Для удобства обозначим стоп кодон как ‘e’.

В первом примере после удаления нуклеотидов под номером 3 3 получим последовательность нуклеотидов AUGUGA, разобьём её на кодоны AUG, UGA — это соответствует белку Me. Его длина равна 2.